package com.leetcode.Hash求解.两数之和;

import java.util.HashMap;
import java.util.Map;

/**
 * <p>
 * 参考：https://leetcode-cn.com/problems/two-sum/
 * </p>
 *
 * @author: Sunny
 * @date: 2021/3/5
 * @version: v1.0.0
 */
public class Main {

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] indexs = searchIndex(nums, target);
        for (int i = 0; i < indexs.length; i++) {
            System.out.println(indexs[i]);
        }
    }

    /**
     * 通过Hash，，O(N)=n
     * @param nums
     * @param target
     * @return
     */
    public static int[] searchIndex(int[] nums, int target) {
        int[] indexs = new int[2];
        Map<Integer, Integer> hash = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (hash.containsKey(nums[i])) {
                indexs[0] = hash.get(nums[i]);
                indexs[1] = i;
                return indexs;
            }
            hash.put(target - nums[i], i);
        }
        return indexs;
    }

//    /**
//     * 2次for循环解决，O(N)=n^2
//     * @param nums
//     * @param target
//     * @return
//     */
//    public static int[] searchIndex(int[] nums, int target) {
//        for (int i = 0; i < nums.length; i++) {
//            for (int j = 0; i < nums.length; j++) {
//                if (nums[i] + nums[j] == target) {
//                    return new int[]{i, j};
//                }
//            }
//        }
//
//        return null;
//    }

}
